#include <vector>

using namespace std;

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        vector<int> tmp(mat[0]);
        for (int i = 1; i < mat.size(); i++) {
            multiset<int> set;
            for (int& val : tmp) {
                for (int& element : mat[i]) {
                    set.insert(val + element);
                    if (set.size() > k) {
                        set.erase(--set.end());
                    }
                }
            }
            tmp.assign(set.begin(), set.end());
        }
        return tmp.back();
    }
};